#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXSIZE 20
#define EQ(a, b) ((a) == (b))
#define LT(a, b) ((a) < (b))
#define LQ(a, b) ((a) <= (b))
typedef int KeyType;
typedef char InfoType;
typedef struct
{
    KeyType key;
    InfoType otherinfo;
}RedType;
typedef struct
{
    RedType r[MAXSIZE + 1];  // r[0]为哨兵单元
    int length;
}SqList;
// 10.2 Insert sort
// p265 algorithm 10.1
void InsertSort(SqList &L)
{
    for (int i = 2; i < L.length; ++i)
    {
        if (LT(L.r[i].key, L.r[i - 1].key))
        {
            L.r[0] = L.r[i];
            L.r[i] = L.r[i - 1];
            int j;
            for (j = i - 2; LT(L.r[0].key, L.r[j].key); --j)
                L.r[j+1] = L.r[j];
            L.r[j + 1] = L.r[0];
        }
    }
}
// p267 algorithm 10.2
void BinarySort(SqList &L)
{
    for (int i = 2; i <= L.length; ++i)
    {
        L.r[0] = L.r[i];
        int low = 0, high = i - 1;
        while (low <= high)
        {
            int m = (low + high) / 2;
            if (LT(L.r[i].key, L.r[m].key))
                high = m - 1;
            else
                low = m + 1;
        }
        for (int j = i - 1; j >= high + 1; --j)
            L.r[j + 1] = L.r[j];
        L.r[high + 1] = L.r[0];
        // 验证low恒等于high+1
        // printf("%d %d\n", low, high + 1);
    }
}
typedef int RcdType;
typedef struct 
{
    RcdType rc;
    int next;
}SLNode;
typedef struct 
{
    SLNode r[MAXSIZE+1];
    int length;
}SLinkListType;
// p270 algorithm 10.3
void Arrange(SLinkListType &SL)
{
    int p = SL.r[0].next;
    for (int i = 0; i < SL.length; ++i)
    {
        while (p < i)
            p = SL.r[p].next;
        int q = SL.r[p].next;
        if (p != i)
        {
            SLNode temp = SL.r[p];
            SL.r[p] = SL.r[i];
            SL.r[i] = temp;
            SL.r[i].next = p;
        }
        p = q;
    }
}
// p272 algorithm 10.4
void ShellInsert(SqList &L, int dk)
{
    for (int i = dk + 1; i <= L.length; ++i)
    {
        if (LT(L.r[i].key, L.r[i-dk].key))
        {
            L.r[0] = L.r[i];
            int j;
            for (j = i - dk; j > 0 && LT(L.r[0].key, L.r[j].key); j -= dk)
                L.r[j+dk] = L.r[j];
            L.r[j+dk] = L.r[0];
        }
    }
}
// p272 algorithm 10.5
void ShellSort(SqList &L, int dlta[], int t)
{
    for (int k = 0; k < t; ++t)
        ShellInsert(L, dlta[k]);
}

// 10.3 Quick Sort
// p274 algorithm 10.6(b)
int Partition(SqList &L, int low, int high)
{
    L.r[0] = L.r[low];
    int pivotkey = L.r[low].key;
    while (low < high)
    {
        while (low < high && L.r[high].key >= pivotkey)
            --high;
        L.r[low] = L.r[high];
        while (low < high && L.r[low].key <= pivotkey)
            ++low;
        L.r[high] = L.r[low];
    }
    L.r[low] = L.r[0];
    return low;
}
// p275 algorithm 10.7
void QSort(SqList &L, int low, int high)
{
    if (low < high)
    {
        int pivotloc = Partition(L, low, high);
        QSort(L, low, pivotloc-1);
        QSort(L, pivotloc+1, high);
    }
}
// p276 algorithm 10.8
void QuickSort(SqList &L)
{
    QSort(L, 1, L.length);
}

// 10.4 Selection Sort
int SelectMinKey(SqList L, int i)
{
    int min = i;
    for (int j = i+1; j <= L.length; ++j)
    {
        if (L.r[j].key < L.r[min].key)
            min = j;
    }
    return min;
}
// p277 algorithm 10.9
void SelectSort(SqList &L)
{
    for (int i = 1; i < L.length; ++i)
    {
        int j = SelectMinKey(L, i);
        if (i != j)
        {
            L.r[0] = L.r[j];
            L.r[j] = L.r[i];
            L.r[i] = L.r[0];
        }
    }
}

void randSqList(SqList &L)
{
    srand(time(0));
    for (int i = 1; i <= L.length; ++i)
        L.r[i].key = rand() % 100;
}
void showSqList(SqList L)
{
    for (int i = 1; i <= L.length; ++i)
        printf("%3d", L.r[i].key);
    printf("\n");
}
int main(void)
{
    SqList L1;
    L1.length = 20;
    randSqList(L1);
    showSqList(L1);

    // BinarySort(L1);
    QuickSort(L1);
    // SelectSort(L1);

    showSqList(L1);

    return 0;
}